/*
 * @lc app=leetcode.cn id=347 lang=java
 *
 * [347] 前 K 个高频元素
 */

// @lc code=start



class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 使用map存储元素和出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for(int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 创建优先级队列，定义比较器，按照key 的值进行排序---升序
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });

        // 遍历map，将元素加入到优先级队列中---只加入k个元素
        for(Integer key : map.keySet()) {
            if(priorityQueue.size() < k) {
                priorityQueue.add(key);
            } else if(map.get(key) > map.get(priorityQueue.peek())) {
                priorityQueue.poll();
                priorityQueue.add(key);
            }
        }

        // 使用数组存放最终结果
        int[] res = new int[k];
        for(int i = 0; i < k; i++) {
            res[i] = priorityQueue.poll();
        }
        return res;
    }
}
// @lc code=end